package medium._0022.pck;

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses{
  public static void main(String[] args) {
        Solution solution = new GenerateParentheses().new Solution();
        final List<String> strings = solution.generateParenthesis(3);
      System.out.println(strings);
  }
  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<String> generateParenthesis(int n) {
        final ArrayList<String> list = new ArrayList<>();
        generate(0, 0, n, "", list);
        return list;
    }

      private void generate(int left, int right, int n, String str, ArrayList<String> list) {
          if (left == n && right == n) {
              list.add(str);
              return ;
          }

          //左括号：随时可以添加
          if(left < n) {
              generate(left + 1, right, n, str.concat("("), list);
          }
          //右括号：左括号 多于 右括号可以添加
          if (right < left) {
              generate(left, right + 1, n, str.concat(")"), list);
          }
      }
  }
//leetcode submit region end(Prohibit modification and deletion)

}